#include<stdio.h> 
#include<string.h> 
#include<iostream>
#include<malloc.h>

#define slice_time 10 //定义时间片的长度为10

using namespace std;

//定义进程控制块PCB
struct pcb
{
    int id;                //进程号
    int status;            //进程状态  0-Ready,  1-Run,  2-Finish
    int arrive_time;       //进程到达时间
    int time;              //估计运行时间
    int run_time;          //已运行时间
    int wait_time;         //等待时间
    int priority;          //优先级
    struct pcb* next;      //链接指针
};

#define length sizeof(struct pcb)

int cur_time=0;                //系统当前运行时间
int num=0;                     //进程的个数

struct pcb *ready_head=NULL;
struct pcb *pcb_head=NULL;
struct pcb *finish_head=NULL;

/*读文件数据,将文件中给出的进程放入PCB队列，以便后续使用
返回值：  0－失败    1－成功*/
int readData()
{ 
    FILE *fp; 
    char fname[20]; 
    cout<<"注意：文件中应包含以下信息：\n";
    cout<<"进程ID    到达时间     估计运行时间     优先级\n";
    cout<<"并且应按到达时间顺序排列!\n\n";
    cout<<"请输入进程流文件名:"; 
    cin>>fname; 
    if((fp=fopen(fname,"r"))==NULL)
    { 
        cout<<"错误,文件打不开,请检查文件名"<<endl; 
        return 0;
    } 
    else
    { 
        //建立PCB链表
        struct pcb  *p1, *p2;
        pcb_head=NULL;
        p1=p2=(struct pcb*)malloc(length);
        if(fscanf(fp,"%d %d %d %d",&p1->id,&p1->arrive_time,&p1->time,&p1->priority) != 4)
        {
            free(p1);
            fclose(fp);
            return 0;
        }
        p1->status=0; p1->run_time=0;  p1->wait_time=0;   //初始化
        while(fscanf(fp,"%d %d %d %d",&p1->id,&p1->arrive_time,&p1->time,&p1->priority) == 4)
        {
            num++;            
            if(num==1)
            {
                pcb_head=p1;
                p1->next=NULL;
            }
            else
                p2->next=p1;
            p2=p1;
            p1=(struct pcb*)malloc(length);
            p1->status=0; p1->run_time=0;  p1->wait_time=0;
        } 
        p2->next=NULL;
        fclose(fp);
        return 1; 
    }
}

//建立就绪队列(前提：PCB队列是按到达时间排序的)
//返回值： 0－就绪队列空   1－就绪队列不空
int readyProcess()
{
    struct pcb *p1, *pready;
    p1=pcb_head;
    pready=ready_head;
    
    //将pready指向就绪队列最后一个结点
    if(pready)
    {
        while(pready->next)
        {
            pready=pready->next; 
        }
    }
    
    /*将新到达进程插入就绪队列末尾*/
    while(p1)
    {
        if(p1->arrive_time<=cur_time)
        {
            if(pready)
            {
                pready->next=p1;
            }
            if(ready_head==NULL)
            {
                ready_head=p1;
            }
            pready=p1;
            p1=p1->next;
            pready->next=NULL;
        }
        else
        {
            pcb_head=p1;   //确定新的PCB队列头
            if(ready_head)
            {
                return 1;    //就绪队列中有元素
            }
            else
            {
                return 0;
            }
        }
    }
    if(p1==NULL)  //已经处理完PCB队列中的结点，将pcb队列头赋NULL
    {
        pcb_head=NULL;
    }
    if(ready_head)
    {
        return 1;    //就绪队列中有元素
    }
    else
    {
        return 0;
    }
}

/*轮转算法中时间片用完的进程插入就绪队列的末尾*/
//参数：p-插入的进程
void insertReadyQueueByRR(struct pcb* p)
{
    struct pcb *pready;

    readyProcess();    //若有新进程进入系统，先将其放入就绪队列
    if(ready_head==NULL)   
    {
        ready_head=p;
        p->next=NULL;
        return;
    }

    pready=ready_head;
    //将pready指向就绪队列最后一个结点
    while(pready->next)
        pready=pready->next; 

    pready->next=p;
    p->next=NULL;
}

//从就绪队列中取出一个就绪进程
//返回值  p－从队列中取出的进程      0－就绪队列空，无进程取出
pcb* getReadyProcessByFIFO()
{
    struct pcb * p;
    if(ready_head)
    {
        p=ready_head;
        ready_head=ready_head->next;
        p->next=NULL;
        return p;
    }
    else
        return 0;
}

//时间片轮转算法
void runProcessByRR()
{
    struct pcb *p, *pFinish=NULL;
    int  t=0,t_sum=0;
    float w=0.0, w_sum=0.0;

    //输出RR算法执行流 
    cout<<endl<<"*****************************************************"<<endl; 
    cout<<"RR算法执行流:"<<endl; cout<<"进程名   本次开始时间    本次结束时间    周转时间    带权周转时间"<<endl; 

    ready_head=NULL;
    while(pcb_head||ready_head)
    {
        while(1)
        {
            if(readyProcess())
            {
                p=getReadyProcessByFIFO();
                break;
            }
            else
                cur_time++;
        }
        p->status=1;
        cout<<p->id<<"\t\t"<<cur_time<<"\t\t";

        if(p->time-p->run_time>slice_time)   //判断本次时间片用完，该进程是否能“运行”完
        { 
            cur_time+=slice_time;
            p->run_time+=slice_time;  
            cout<<cur_time<<endl;            
            p->status=0;
            insertReadyQueueByRR(p);
        }
        else
        { 
            cur_time=cur_time+p->time-p->run_time;
			cout<<cur_time<<"\t";
			//统计数据
			t=cur_time-p->arrive_time;

			t_sum+=t;
			cout<<t<<"\t\t";
			w=(float)t/p->time;
			w_sum+=w;
			cout<<w<<endl;

			p->status=2;
			if(finish_head==NULL)  
				finish_head=pFinish=p;
			else
				pFinish->next=p;
			p->next=NULL;
			pFinish=pFinish->next;
		}
	}
	cout<<"平均周转时间为："<<(float)t_sum/num<<"\t"<<"平均带权周转时间为："<<(float)w_sum/num<<endl;
}

int main()
{
	if(readData())
	runProcessByRR();
	return 0;
}